from typing import *
from sortedcontainers import SortedList
from bisect import bisect_left


class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        rooms.sort(key=lambda a: a[1], reverse=True)
        idx = [i for i in range(len(queries))]
        idx.sort(key=lambda a: queries[a][1], reverse=True)
        ans = [-1] * len(queries)
        sl = SortedList()
        j = 0
        for i in range(len(queries)):
            preferredj, minSizej = queries[idx[i]]
            while j < len(rooms) and rooms[j][1] >= minSizej:
                sl.add(rooms[j][0])
                j += 1
            if len(sl) == 0:
                continue
            b = bisect_left(sl, preferredj,hi=len(sl) - 1)
            ans[idx[i]] = sl[b] 
            if b > 0 and abs(sl[b-1] - preferredj) <= abs(sl[b] - preferredj):
                ans[idx[i]] = sl[b-1]
        return ans


s = Solution()
print(s.closestRoom(rooms=[[2, 2], [1, 2], [3, 2]], queries=[[3, 1], [3, 3], [5, 2]]) == [3,-1,3])
print(s.closestRoom(rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]) == [2,1,3])